package Array.Simulation;
/**
 * 描述
 * 一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，
 * 即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）（
 * 最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
 *
 * 数据范围：0 <n≤100，0≤m≤1000
 * 进阶：空间复杂度 O(1)，时间复杂度 O(n)
 * 示例1
 * 输入：
 * 6,2,[1,2,3,4,5,6]
 * 返回值：
 * [5,6,1,2,3,4]
 * 示例2
 * 输入：
 * 4,0,[1,2,3,4]
 * 返回值：
 * [1,2,3,4]
 *
 * */
class BM97 {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] a) {
        // write code here
        //不移动
        if(m==0){
            return a;
        }
        int len = m%n;
        /**
         * 右旋转和左旋转都是三次反转就可完成
         * 右旋转是值将末尾的n个元素移到开头，整体反转后，将两段分别反转即所求
         * 左旋转是将开头的n个元素移到末尾，整体反转后,再把两段分别反转即所求
         * */
        reverse(a,0,a.length-1);
        reverse(a,0,len-1);
        reverse(a,len,a.length-1);
        return a;
    }

    private void reverse(int[] a, int start, int end){
        //左闭右闭
        while(start<end){
            int temp = a[start];
            a[start] = a[end];
            a[end] = temp;
            start++;
            end--;
        }
    }
}
